/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
 var findLadders = function(beginWord, endWord, wordList) {
    let ans = []
    
      // 确保 beginWord, endWord 都在字典中
      const wordSet = new Set(wordList)
      if (!wordSet.has(endWord)) return ans
      wordSet.add(beginWord)
      
      // 双向BFS构建有向无环图 dag
      let dag = bfs(beginWord, endWord, wordSet)
      if (!dag) return ans
      // DFS在有向无环图dag中收集连通路径，BFS已确保连通路径最短
      // NOTICE:
      // dag 中虽然无环，但不同路径可能会经过相同的节点，可能导致大量重复计算.
      // dp.get(word)
      // * undefined: 表示未访问过 word
      // * pathListToEnd: 表示访问过 word ，从 word 出发到达 endWord 的所有路径为 pathListToEnd
      let dp = new Map()
      // NOTICE: [[]] 表示有路径，但长度为0。 如果只是 [] ，表示没有路径可以到达终点
      dp.set(endWord, [[]])
      dfs([beginWord], dag, ans, dp)
      return ans
    
      // 时空复杂度: O(NL^2) <= T((N+M)*L*26*(L+2L+L)) <= O((NL)^2), 最坏 S(N)=O(N)
      // N = 节点总数，M = 边总数，L = 单词长度
      function bfs (beginWord, endWord, wordSet) {
        const CODE_A = 'a'.charCodeAt(0), CODE_Z = 'z'.charCodeAt(0)
        const L = beginWord.length
        let dag = new Map()
        // 每层写入 dag 的增量数据，同时用于省略 newQueue1 。
        // 如果从当前层的节点延伸出的边不能连通双向BFS，那么保存下一层的节点；
        // 如果能连通，那么仅保存下一层的节点中能实现连通的节点。
        let dagPatch = new Map()
        // 优化：有可能经过不同的路径，在同一层到达相同的节点，所以 queue 中节点可以去重，减少计算量
        let queue1 = new Set([beginWord]), queue2 = new Set([endWord])
        // 用于避免BFS回头，因为字典本质是无向图
        let visited1 = new Set([beginWord]), visited2 = new Set([endWord])
        let isFromBegin = true, isConnected = false
        // 遍历完一层后，只要有一个方向的队列为空，就表示无法连通
        while (queue1.size && queue2.size) {
          // NOTICE: 每层重复使用 dagPatch ，要重置
          dagPatch.clear()
          if (queue1.size > queue2.size) {
            ;[queue1, queue2, visited1, visited2] = [queue2, queue1, visited2, visited1]
            isFromBegin = !isFromBegin
          }
          for (const prevWord of queue1) { // 软出队
            for (let i = 0; i < L; ++i) { // T(L)
              for (let j = CODE_A; j <= CODE_Z; ++j) { // T(26)
                const char = String.fromCharCode(j)
                if (char === prevWord[i]) continue // 跳过跟自身相同的单词
                const curWord = prevWord.slice(0, i) + String.fromCharCode(j) + prevWord.slice(i + 1) // T(L)
                if (!wordSet.has(curWord) || visited1.has(curWord)) continue // T(2L)
                if (visited2.has(curWord)) { // T(L)
                  if (!isConnected) {
                    isConnected = true
                    // 小优化：同一层中，在遇到连通双向BFS的边之前，可能会先遇到不能实现连通的边，可以清除，接下来只保存能连通双向BFS的边
                    dagPatch.clear()
                  }
                  mapAddValIntoSet(dagPatch, prevWord, curWord)
                }
                else {
                  if (!isConnected) mapAddValIntoSet(dagPatch, prevWord, curWord)
                }
              }
            }
          }
          queue1.clear() // 真实出队
    
          // NOTICE: 
          // 层操作: 将 dagPatch 中的数据更新到 dag, queue1, visited1 中。
          // 因为当前层可能有A, B两个节点指向下一层的相同节点C，
          // 如果不在遍历完一层后统一操作，而是遍历的同时操作，
          // 那么遍历到A的边时会把C记录为已访问，于是遍历到B的边时会跳过C，导致丢失目标路径。
          for (const [key, values] of dagPatch) {
            for (const val of values) {
              // NOTICE: 更新 dag 时注意方向
              isFromBegin ? mapAddValIntoSet(dag, key, val) : mapAddValIntoSet(dag, val, key)
              if (isConnected) continue // 小优化：如果已连通，queue1, visited1 不会再用到，省去计算
              queue1.add(val)
              visited1.add(val)
            }
          }
    
          if (isConnected) return dag
        }
        // NOTICE: 有可能不连通
        return isConnected ? dag : null
      }
    
      function mapAddValIntoSet (map, key, val) {
        let values = map.get(key)
        if (!values) {
          values = new Set()
          values.add(val)
          map.set(key, values)
        }
        else values.add(val)
      }
    
      // 时空复杂度: T(NlogN), S(logN)
      function dfs (path, dag, ans, dp) {
        const word = path[path.length - 1]
        // 使用 dp 剪枝优化。终点检测已包含 dp 中
        let pathListToEnd = dp.get(word)
        if (pathListToEnd) {
          for (let pathToEnd of pathListToEnd) {
            ans.push(path.concat(pathToEnd))
          }
          return
        }
    
        const nextWords = dag.get(word)
        if (!nextWords || !nextWords.size) return // 不连通的路径
    
        const oldPathLength = path.length
        const oldAnsLength = ans.length
        for (const nextWord of nextWords) {
          path.push(nextWord)
          dfs(path, dag, ans, dp)
          path.pop() // 回溯
        }
    
        // 更新 dp
        pathListToEnd = ans.length === oldAnsLength ?
          [] :
          // BUGFIX: pathListToEnd 中不包含 word
          ans.slice(oldAnsLength).map(ansPath => ansPath.slice(oldPathLength))
        dp.set(word, pathListToEnd)
      }
    }